package com.banmoon.algorithm.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Question2055 {

    public static void main(String[] args) {
        int[][] ints = {{1, 17}, {4, 5}, {14, 17}, {5, 11}, {15, 16}};
        int[] result = platesBetweenCandles("***|**|*****|**||**|*", ints);
        System.out.println(Arrays.toString(result));
    }

    public static int[] platesBetweenCandles(String s, int[][] queries) {
        char[] str = s.toCharArray();
        int[] result = new int[queries.length];
        int[] plates = new int[str.length];//plates[i]表示[0,i]之间有多少盘子
        int count = 0;
        for (int i = 0; i < str.length; i++) {
            if (str[i] == '*') count++;
            plates[i] = count;
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < str.length; i++) {
            if (str[i] == '|') {
                list.add(i);
            }
        }
        //array[i]表示第i个蜡烛的索引
        Integer[] array = list.toArray(new Integer[list.size()]);
        for (int i = 0; i < queries.length; ) {
            // 如果起点和终点相同，则说明没有盘子
            if ((queries[i][1] - queries[i][0]) == 0) {
                result[i++] = 0;
                continue;
            }
            //binarySearch(object[ ], object key);
            //如果key在数组中，则返回搜索值的索引；否则返回-1或者插入点是索引键将要插入数组的那一点，即第一个大于该键的元素索引+1
            //二分查找[a,b]中最接近a右边的蜡烛索引和最接近b左边的蜡烛索引，然后plates[right]-plate[left]即答案
            int start = (Arrays.binarySearch(array, queries[i][0]) >= 0) ? Arrays.binarySearch(array, queries[i][0]) : -Arrays.binarySearch(array, queries[i][0]) - 1;
            int end = (Arrays.binarySearch(array, queries[i][1]) >= 0) ? Arrays.binarySearch(array, queries[i][1]) : -Arrays.binarySearch(array, queries[i][1]) - 2;
            if (start >= end) {
                result[i++] = 0;
                continue;
            }
            result[i++] = plates[array[end]] - plates[array[start]];
        }
        return result;
    }

    /**
     * 超时
     *
     * @param s
     * @param queries
     * @return
     */
    public static int[] platesBetweenCandles1(String s, int[][] queries) {
        char[] chars = s.toCharArray();
        int[] result = new int[queries.length];
        for (int k = 0; k < queries.length; k++) {
            int start = queries[k][0];
            int end = queries[k][1];
            int num = 0;
            int st = s.indexOf("|", start);
            int en = s.lastIndexOf("|", end);
            for (int i = st; i < en; i++) {
                if ('*' == chars[i])
                    num++;
            }
            result[k] = num;
        }
        return result;
    }
}
